/*
    稳定婚姻问题就是给你n个男的，n个女的，
然后给你每个男生中女生的排名，和女生心目中男生的排名，
然后让你匹配成n对，使婚姻稳定，
    假如a和b匹配,c和d匹配，如果a认为d比b好，同时d也认为a比c好，那么ad就有可能私奔，
这样就导致了婚姻的不稳定，稳定婚姻就是找到一种解决方案让婚姻稳定
    通常是使用GS算法
    稳定婚姻问题必定有解
*/
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <stack>
using namespace std;
const int MAXN=4;
const int NOT=-1;
//获取man在lady中的排行
int getPositionFromLady(int ladyArray[][MAXN],int lady,int man){
    for(int i=0;i<MAXN;i++){
        if(ladyArray[lady][i]==man){
            return i;
        }
    }
    return NOT;
}
void choosePartner(stack<int>& manStack,int manPos,int manArray[][MAXN],int ladyArray[][MAXN],int manPrefer[],int manStartPos[],int ladyNow[]){
    //选择排名第一的lady
    int preferLady=manArray[manPos][manStartPos[manPos]];
    if(ladyNow[preferLady]==NOT){
        ladyNow[preferLady]=manPos;
        manPrefer[manPos]=preferLady;
    }
    else{
        int oldPos=getPositionFromLady(ladyArray,preferLady,ladyNow[preferLady]);
        int newPos=getPositionFromLady(ladyArray,preferLady,manPos);
        if(oldPos<newPos){
            manStartPos[manPos]++;
            manStack.push(manPos);
        }
        else{
            manStartPos[ladyNow[preferLady]]++;
            manStack.push(ladyNow[preferLady]);
            ladyNow[preferLady]=manPos;
            manPrefer[manPos]=preferLady;
        }
    }
}
int main(void){
    int manArray[MAXN][MAXN]={{2,3,1,0},{2,1,3,0},{0,2,3,1},{1,3,2,0}};
    int ladyArray[MAXN][MAXN]={{0,3,2,1},{0,1,2,3},{0,2,3,1},{1,0,3,2}};
    int manPrefer[MAXN]={0};
    int manStartPos[MAXN]={0};
    int ladyNow[MAXN]={NOT};

    stack<int> manStack;
    for(int pos=0;pos<MAXN;pos++){
        choosePartner(manStack,pos,manArray,ladyArray,manPrefer,manStartPos,ladyNow);
    }
    while(manStack.size()!=0){
        int manPos=manStack.top();
        manStack.pop();
        choosePartner(manStack, manPos, manArray, ladyArray, manPrefer, manStartPos,ladyNow);
    }
    for(int i=0;i<MAXN;i++){
        printf("Man NO.: %d  Lady NO.: %d\n",i,manPrefer[i]);
    }
    return 0;
}
